package com.fengdi.solutions.hard;


/**
 * @author FengDi
 * @Title 233. 数字 1 的个数
 * @Description 给定一个整数 n，计算所有小于等于 n 的非负整数中数字 1 出现的个数。
 * @Solution 以百位数为例，100 = 10**2，在从0到1000的数字中，百位数为1的个数为[100, 199]共100个
 *           对于数字n，其存在Math.floor(n /1000)组循环，故有 Math.floor(n /1000) * 100个百位数为1的数字
 *           而对于n小于1000的部分m：当 m < 100时个数为0，当 m >= 100 且 < 200时 存在 m - 100 + 1个。当 m > 200 时存在100个
 *           由此可总结出对于第k位：count = (n / 10**(k+1)) * 10**k + threshold  + Math.min(Math.max( n % 10**(k+1)) - 10**k + 1, 0), 10**k)
 * */
public class _233_amountOfOne {
    public int countDigitOne(int n) {
        long threshold = 1;
        long count = 0;
        for(int i = 0; n >= threshold; i++) {
            count += (n / (threshold * 10)) * threshold  + Math.min(Math.max( n % (threshold * 10) - threshold + 1, 0), threshold);
            threshold *= 10;
        }
        return (int) count;
    }
}
